class Solution {
public:
    int trap(vector<int>& height) {
        if (height.empty()) return 0;
        
        int sum = 0;
        stack<int> s; 
        
        for (int i = 0; i < height.size(); i++) {

            while (!s.empty() && height[i] > height[s.top()]) {
                int bottom_index = s.top();
                s.pop();
                
                if (s.empty()) break;
                
                int left_index = s.top();
                int h = min(height[left_index], height[i]) - height[bottom_index];
                int w = i - left_index - 1;
                sum += h * w;
            }
            s.push(i);
        }
        return sum;
    }
};